package org.xqh.study.leetcode.algorithm.mineffort;

import java.util.*;

/**
 * @ClassName MinimumEffortPath
 * @Description 最小体力消耗
 * https://leetcode-cn.com/problems/path-with-minimum-effort/
 * @Author xuqianghui
 * @Date 2021/1/30 10:09
 * @Version 1.0
 */
public class MinimumEffortPath {

    public static void main(String[] args) {
        int[][] heights = {{1,2,2},{3,8,2},{5,3,5}};
        System.out.println(minimumEffortPath(heights));
    }

    /**
     * 并查集  解法
     * 1. rows * cols 个节点 , 只要 左上角 和 右下角 方格 具有连通性
     *
     * @param heights
     * @return
     */
    public static int minimumEffortPath(int[][] heights) {
        int rows = heights.length;//行
        int cols = heights[0].length;//列
        int size = rows * cols;

        //对相邻方格 计算对应的 高度差
        List<int[]> list = new ArrayList<>();
        // 每个方格 对比 其右边+下边 方格 高度差
        for(int i = 0; i < rows; i ++){
            for(int j = 0; j < cols; j ++){
                int idx = i * cols + j;//当前 方格序号
                //每行 相邻方格高度差
                if(j > 0){
                    list.add(new int[]{idx - 1, idx, Math.abs(heights[i][j] - heights[i][j-1])});
                }

                //每列 相邻方格高度差
                if(i > 0){
                    list.add(new int[]{idx - cols, idx, Math.abs(heights[i][j] - heights[i - 1][j])});
                }
            }
        }
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        // 对应 rows * cols 个节点
        UnionFind union = new UnionFind(size);
        int result = 0;
        for(int[] items:list){
            union.union(items[0], items[1]);
            if(items[2] > result){
                result = items[2];
            }
            if(union.connected(0, size - 1)){
                break;
            }
        }
        return result;
    }

    public static class UnionFind {
        int[] parent;
        int[] size;//节点深度
        int setCount;//联通分量 数量


        public UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            setCount = n;
            Arrays.fill(size, 1);//节点深度默认都是1
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public void union(int x, int y) {
            x = find(x);
            y = find(y);

            if(x == y){
                return ;
            }
            if (size[x] < size[y]) {
                int tmp = x;
                x = y;
                y = tmp;
            }
            parent[y] = x;
            size[x] += size[y];
            --setCount;
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public boolean connected(int x, int y) {
            return find(x) == find(y);
        }
    }


    public static int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//上下左右 行列坐标值相加

    /**
     * 无向图 连通性 广度优先搜素 二分法
     * 看了 题解 自己码了一遍
     *
     * @param heights
     * @return
     */
    public static int minimumEffortPath3(int[][] heights) {
        int m = heights.length; //方格 行 数量
        int n = heights[0].length; //方格 列 数量

        /**
         * 二分法查找
         * 因为题目限定  1< heights[i][j] <= 10的6次方
         */
        int left = 0, right = 999999, ans = 0;
        while (left <= right) {

            /**
             * 对方格做标记 heights[i][j] 对应 mark[n * i + j]
             */
            boolean[] mark = new boolean[m * n];
            Queue<int[]> pathQueue = new LinkedList<>();
            pathQueue.offer(new int[]{0, 0});//初始 放入 左上角 坐标
            mark[0] = true;//标识 第一个坐标 已经处理
            int mid = (left + right) / 2;//找到中间数字, 做对比 假设 该路径 权重 之和 <= mid
            //循环 寻找 路径
            while (!pathQueue.isEmpty()) {
                int[] cell = pathQueue.poll();//取出队列中的值
                //取出 当前处理坐标 的 行 x, 列  y
                int x = cell[0];
                int y = cell[1];
                //可以 向四个方向移动
                for (int i = 0; i < 4; i++) {
                    //计算出 要移动的 方格 行列 坐标
                    int nx = x + direction[i][0];
                    int ny = y + direction[i][1];
                    //判断 边界
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && !mark[n * nx + ny] && Math.abs(heights[nx][ny] - heights[x][y]) <= mid) {
                        //将当前 方格坐标 放入 队列
                        pathQueue.offer(new int[]{nx, ny});
                        mark[n * nx + ny] = true;
                    }
                }
            }

            if (mark[m * n - 1]) {//该路径 能走到 最右下角 方格
                //检索 mid 右侧
                right = mid - 1;
                ans = mid;
            } else {//
                left = mid + 1;
            }
        }
        return ans;
    }


    /**
     * 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，
     * 其中 heights[row][col] 表示格子 (row, col) 的高度。
     * 一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) 
     * （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，
     * 你想要找到耗费 体力 最小的一条路径。
     *
     * @param heights
     * @return
     */
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    /**
     * 二分法查找
     *
     * @param heights
     * @return
     */
    public int minimumEffortPath2(int[][] heights) {
        int m = heights.length;// 方格 行数
        int n = heights[0].length;//方格列数
        int left = 0, right = 999999, ans = 0;//题目限定 最高 10的6次方
        while (left <= right) {
            int mid = (left + right) / 2;
            Queue<int[]> queue = new LinkedList<int[]>();
            queue.offer(new int[]{0, 0});//初始
            boolean[] seen = new boolean[m * n];//记录走过 的 路径
            seen[0] = true;
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];//取出 行 列 坐标
                for (int i = 0; i < 4; ++i) {// 上下左右 四个 方向移动
                    int nx = x + dirs[i][0];//移动后的 行 坐标
                    int ny = y + dirs[i][1];//移动后的列 坐标
                    /**
                     * nx >= 0 && nx < m && ny >= 0 && ny < n  : 判断 行列 边界.
                     * !seen[nx * n + ny] 该 坐标 没有 标记过
                     * Math.abs(heights[x][y] - heights[nx][ny]) <= mid 高度差 小于 二分查找值
                     */
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && !seen[nx * n + ny] && Math.abs(heights[x][y] - heights[nx][ny]) <= mid) {
                        queue.offer(new int[]{nx, ny});//放入 下一个 可移动 坐标
                        seen[nx * n + ny] = true;//标识当前 坐标 已经 标识 不再处理.
                    }
                }
            }
            if (seen[m * n - 1]) {//右下角坐标已经处理(说明 能找到 左上角 到 右下角的 路径) 设置 当前 这次 查找  返回 值.
                ans = mid;
                right = mid - 1;// 下一次 二分法查找 , 左边界
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

}
